A content addressable memory (CAM) system is a storage system that can be instructed to compare a specific pattern of comparand data with data stored in its associative CAM array. The entire CAM array, or segments thereof, is searched in parallel for a match with the comparand data. The CAM device typically includes a priority encoder to translate the highest priority matching location into a match address or CAM index, which is sometimes referred to as the highest priority match (HPM).
The CAM array includes a plurality of rows of CAM cells, where bits stored in a row are typically referred to a data word. U.S. Pat. No. 5,440,715 describes a technique for expanding the width of the data words beyond that of a single row of CAM cells. Multiple data words can be width expanded together to form a data line. It appears, however, that the CAM system of the '715 patent will not always output the correct match address. For example, assume a first data line of two data words ZY is stored in data words 0 and 1, respectively, and a second data line of two data words WZ is stored in data words 2 and 3, respectively. When a comparand data line of WZ is provided for comparison, the first cycle compare with W will indicate a match with data word 2 only. The second cycle compare with Z will indicate a match with data words 0 and 3 and match lines ML0 and ML3 will be activated. When the priority encoder is enabled, it will output a match address of 0 instead of 3 since ML0 is the highest priority match line.
Additionally, it appears that the CAM system of the '715 patent will not always function correctly when each data line has different numbers of data words. For example, assume that a data line of 5 words VWXYZ is loaded into data word locations 0-4, and a data line of 4 words VWXY is loaded into data word locations 5-8. When a comparand data line of VWXY is provided to the CAM array, ML3 and ML8 will both be activated and the priority encoder will incorrectly output an address of three that stores the last word of a five word data line and not the last word of a four word entry.
U.S. Pat. No. 6,252,789 discloses an inter-row configurable CAM device that solves the above-mentioned disadvantages of the CAM system of the '715 patent by including a word expansion logic (WEL) circuit in each row of CAM cells. The WEL controls whether one or more consecutive rows of CAM cells are sequentially connected in a chain to form a data word chain that spans across multiple rows of the CAM array. More specifically, the WELs in all CAM rows that store the data words of the chain are configured to logically combine (e.g., AND) the match signals of the current CAM row and the previous adjacent CAM row and to forward the combined match signals to the next adjacent CAM row, and the WEL in the CAM row that stores the last data word outputs the match signals to the priority encoder. In this manner, the CAM device of the '789 can be configured to perform string match operations on words having very large lengths.
Unfortunately, because the WEL in a CAM row can combine the row's match state only with the match state of an adjacent CAM row to generate an output match signal, and then can route the row's output match signal to only another adjacent CAM row, the row output match states can only be shifted sequentially across the array one row at a time.
Further, because data word chains must be stored in contiguous rows of the '789 CAM array, there may be many available (e.g., un-occupied) rows scattered across the array that cannot be used to store data word chains because the available rows are not contiguous, thereby resulting in unutilized memory area. For example, if there 30 available non-contiguous rows in the '789 CAM array, the only way to store chains having more than one data word is to re-arrange the stored entries to free a block of contiguous rows. Unfortunately, table management tools that re-arrange able contents are burdensome and time consuming.
Further, because match signals from a CAM row in the '789 patent can be routed to only one adjacent row at a time, it is not feasible to store large numbers of regular expressions in the CAM device of the '789 patent. For example, to store the regular expression REG1=“ab(cd|ef|gh)uv” in the '789 CAM device, the REG1 must first be unrolled to generate all possible strings that can match REG1, which includes S1=“abcduv,” S2=“abefuv,” and S3=“abghuv.” Then, the individual strings must be stored separately as 3 data word chains in 3 corresponding sets of contiguous CAM rows. Thus, for example, if each CAM row includes 8 CAM cells to store an 8-bit ASCII encoded character, then a first set of 6 contiguous CAM rows of the '789 patent are required to store S1=“abcduv,” a second set of 6 contiguous CAM rows are required to store S2=“abefuv,” and a third set of 6 contiguous CAM rows are required to store S3=“abghuv,” thereby requiring 18 contiguous rows in the '789 patent to store a regular expression that, in its original (e.g., rolled) form, includes only 10 characters.
Thus, there is a need for a device to have the capability to selectively connect any number of arbitrarily selected CAM rows together in a chain so that data words spanning multiple CAM rows can be stored in any available CAM rows in the array, without regard to their physical locations relative to one another. Further, there is a need for a device to have the capability to route the match signals from each CAM row to any number of other arbitrarily selected or located CAM rows at the same time so that regular expressions having logical operators can be stored in the CAM array in their unrolled form, thereby minimizing the amount of CAM rows required to store regular expressions.
Like reference numerals refer to corresponding parts throughout the drawing figures.